package com.suanfa.matrix;

/**
 * 矩阵中找到给定字符串
 */
public class Words {

    boolean[][] vis;

    int[][] step = {{-1,0},{0, 1},{1,0},{0, -1}};


    public boolean getChars(char[][] board, String word, int r, int c){
        int m = board.length;
        int n = board[0].length;
        int[][] vis = new int[m][n];
        char[] ch = word.toCharArray();
        for(int i=0; i<m; i++){
            for(int j = 0; j< n; j++){
                char s = board[i][j];
                if(s == ch[0]){//找到开头，开始深度搜索

                }
            }
        }
        return false;
    }



    public boolean getChars(char[][] board, char[] word, int index, int r, int c){
        if(index == word.length){
            return board[r][c] == word[index];
        }
        boolean result = false;
        for(int i = 0; i< step.length; i++){
            int x = r+step[i][0];
            int y = c+step[i][1];
            if(inArea(board,x, y) && !vis[x][y]){
                boolean flag = getChars(board, word, index + 1, x, y);
                if(flag){
                    result = true;
                    break;
                }
            }

        }

        return  result;
    }


    private boolean inArea(char[][] arr, int r, int c){
        return r>=0 && r< arr.length&& c>=0 && c< arr[0].length;
    }
}
